import java.util.*;

/**
 * @author 雷明浩
 * @date 2025/8/22 17:34
 */
public class FindOrder {
    private boolean[] vis;
    private ArrayList<Integer> path;
    // map记录有哪些数字在当前数字之前
    private Map<Integer, Set<Integer>> map;
    public ArrayList<Integer> findOrder (int numProject, ArrayList<ArrayList<Integer>> groups) {
        // write code here
        vis = new boolean[numProject];
        path = new ArrayList<>();
        map = new HashMap<>();
        groups.forEach(group -> {
            Set<Integer> set = map.get(group.get(0));
            if (set == null) {
                set = new HashSet<>();
            }
            set.add(group.get(1));
            map.put(group.get(0), set);
        });
        return dfs(numProject, groups);
    }

    private ArrayList<Integer> dfs(int numProject, ArrayList<ArrayList<Integer>> groups) {
        if (path.size() >= numProject) {
            return path;
        }
        for (int i = 0; i < numProject; i++) {
            if (!vis[i]) {
                boolean flg = false;
                Set<Integer> set = map.get(i);
                if (set != null) {
                    for (int num : map.get(i)) {
                        if (!vis[num]) {
                            flg = true;
                            break;
                        }
                    }
                }
                if (!flg) {
                    vis[i] = true;
                    path.add(i);
                    ArrayList<Integer> result = dfs(numProject, groups);
                    if (result != null && result.size() == numProject) {
                        return result;
                    }
                    vis[i] = false;
                    path.remove(path.size() - 1);
                }
            }
        }
        return new ArrayList<>();
    }

    public static void main(String[] args) {
        FindOrder findOrder = new FindOrder();
        ArrayList<ArrayList<Integer>> groups = new ArrayList<>();
        ArrayList<Integer> list1 = new ArrayList<>();
        list1.add(1);
        list1.add(2);
        groups.add(list1);
        findOrder.findOrder(4, groups).forEach(System.out::println);
    }
}